CODE 86. Permutations II

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/10/20/2013-10-20-CODE 86 Permutations II/

访问原文「CODE 86. Permutations II」

Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1],
and [2,1,1].

public ArrayList<ArrayList<Integer>> permute(int[] num) {
	// Note: The Solution object is instantiated only once and is reused by
	// each test case.
	ArrayList<Integer> numbers = new ArrayList<Integer>();
	for (int n : num) {
		numbers.add(n);
	}
	ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>>(
			dfs(numbers));
	return results;
}

Set<ArrayList<Integer>> dfs(ArrayList<Integer> numbers) {
	if (numbers.size() <= 1) {
		Set<ArrayList<Integer>> results = new HashSet<ArrayList<Integer>>();
		ArrayList<Integer> result = new ArrayList<Integer>(numbers);
		results.add(result);
		return results;
	}
	Set<ArrayList<Integer>> results = new HashSet<ArrayList<Integer>>();
	ArrayList<Integer> newNumbers = new ArrayList<Integer>(numbers);
	for (int i = 0; i < numbers.size(); i++) {
		Integer number = numbers.get(i);
		newNumbers.remove(number);
		Set<ArrayList<Integer>> res = dfs(newNumbers);
		for (ArrayList<Integer> re : res) {
			re.add(0, number);
			results.add(re);
		}
		newNumbers.add(number);
	}
	return results;
}